CF794F Leha and security system

一道神奇的线段树...

题目要求区间修改，区间查询，很容易想到线段树，但是怎么维护每一位数字呢？

显然，我们将每位拆分，对于每一个数字维护他的贡献，如 $1221123$ 中 $1$ 的贡献为 $1001100$ , $2$ 的贡献为 $110010$。于是，我们需要$10$棵线段树，维护$0-9$的贡献。

修改很简单，如果将$x$改为$y$，注意区间有懒标记时要比较懒标记（因为该区间的数字在下传时会变），将区间懒标记为$x$的改为$y$，统计贡献，同时更改懒标记。

最后统计答案时，将区间数字的贡献乘上该位的数字，求和即可。

最关键的是懒标记下传，将子树懒标记不同的加入到贡献里，再将子树懒标记修改，注意改变后可能会影响答案，建议先用变量存储再赋值。

#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1

const int MAXN = 100000;
int n , k , a[ MAXN + 5 ];
struct Point{
	int l , r , Lazy;
    long long sum;
};
struct Segment_Tree{
	Point Tree[ 10 ][ 4 * MAXN + 5 ];
	
	void Pushup( int x ) {
		for( int i = 0 ; i <= 9 ; i ++ )
			Tree[ i ][ x ].sum = Tree[ i ][ ls ].sum + Tree[ i ][ rs ].sum;
	}
	void Pushdown( int x ) {
		int lazy[ 15 ];
        long long sum[ 15 ];
		
		for( int i = 0 ; i <= 9 ; i ++ )
			lazy[ i ] = Tree[ i ][ ls ].Lazy , sum[ i ] = Tree[ i ][ ls ].sum;
		for( int i = 0 ; i <= 9 ; i ++ ) {
			if( Tree[ i ][ x ].Lazy == i ) continue;
			for( int j = 0 ; j <= 9 ; j ++ )
				if( Tree[ j ][ ls ].Lazy == i ) lazy[ j ] = Tree[ i ][ x ].Lazy;
			sum[ Tree[ i ][ x ].Lazy ] += Tree[ i ][ ls ].sum;
			sum[ i ] -= Tree[ i ][ ls ].sum;
		}
		for( int i = 0 ; i <= 9 ; i ++ )
			Tree[ i ][ ls ].Lazy = lazy[ i ] , Tree[ i ][ ls ].sum = sum[ i ];
		
		for( int i = 0 ; i <= 9 ; i ++ )
			lazy[ i ] = Tree[ i ][ rs ].Lazy , sum[ i ] = Tree[ i ][ rs ].sum;
		for( int i = 0 ; i <= 9 ; i ++ ) {
			if( Tree[ i ][ x ].Lazy == i ) continue;
			for( int j = 0 ; j <= 9 ; j ++ )
				if( Tree[ j ][ rs ].Lazy == i ) lazy[ j ] = Tree[ i ][ x ].Lazy;
			sum[ Tree[ i ][ x ].Lazy ] += Tree[ i ][ rs ].sum;
			sum[ i ] -= Tree[ i ][ rs ].sum;
		}
		for( int i = 0 ; i <= 9 ; i ++ )
			Tree[ i ][ rs ].Lazy = lazy[ i ] , Tree[ i ][ rs ].sum = sum[ i ];
		
		for( int i = 0 ; i <= 9 ; i ++ )
			Tree[ i ][ x ].Lazy = i;
	}
	
	void Build( int x , int l , int r ) {
		for( int i = 0 ; i <= 9 ; i ++ ) {
			Tree[ i ][ x ].l = l , Tree[ i ][ x ].r = r;
			Tree[ i ][ x ].sum = 0 , Tree[ i ][ x ].Lazy = i;
		}
		if( l == r ) {
			int t = 1;
			while( a[ l ] ) {
				Tree[ a[ l ] % 10 ][ x ].sum += t;
				a[ l ] /= 10 , t *= 10;
			}
			return;
		}
		int Mid = ( l + r ) / 2;
		Build( ls , l , Mid );
		Build( rs , Mid + 1 , r );
		Pushup( x );
	}
	void Insert( int x , int l , int r , int dex1 , int dex2 ) {
		if( r < Tree[ 0 ][ x ].l || Tree[ 0 ][ x ].r < l )
			return;
		if( l <= Tree[ 0 ][ x ].l && Tree[ 0 ][ x ].r <= r ) {
			for( int i = 0 ; i <= 9 ; i ++ )	
				if( Tree[ i ][ x ].Lazy == dex1 ) {
					Tree[ dex2 ][ x ].sum += Tree[ dex1 ][ x ].sum;
					Tree[ dex1 ][ x ].sum = 0;
					Tree[ i ][ x ].Lazy = dex2;
				}
			return;
		}
		Pushdown( x );
		Insert( ls , l , r , dex1 , dex2 );
		Insert( rs , l , r , dex1 , dex2 );
		Pushup( x ); 
	}
	long long Find( int x , int l , int r ) {
		if( r < Tree[ 0 ][ x ].l || Tree[ 0 ][ x ].r < l )
			return 0;
		if( l <= Tree[ 0 ][ x ].l && Tree[ 0 ][ x ].r <= r ) {
			long long Ans = 0;
			for( int i = 0 ; i <= 9 ; i ++ )
				Ans += Tree[ i ][ x ].sum * i;
			return Ans;
		}
		Pushdown( x );
		return Find( ls , l ,r ) + Find( rs , l , r );
	}
}Tree;

int op , x , y , l , r;
int main( ) {
	scanf("%d %d",&n,&k);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	Tree.Build( 1 , 1 , n );
	
	for( int i = 1 ; i <= k ; i ++ ) {
		scanf("%d",&op);
		if( op == 1 ) {
			scanf("%d %d %d %d",&l,&r,&x,&y);
			if( x == y ) continue;
			Tree.Insert( 1 , l , r , x , y );
		}
		if( op == 2 ) {
			scanf("%d %d",&l,&r);
			printf("%lld\n",Tree.Find( 1 , l , r ));
		}
	}
	return 0;
}